//
//  BalanceBinaryTree.swift
//  others
//
//  Created by lhc on 2024/8/27.
//

import Foundation

/// 平衡二叉树
class BalanceBinaryTree<T: Comparable, E>: BinaryTree<T, E> {
    /// 获取当前node的高度
    internal func getHeightWithNode(_ node: Node?) -> Int {
        return node?.height ?? 0
    }
    
    /// 获得当前node的平衡因子
    internal func getBalanceFactor(node: Node?) -> Int {
        guard let node = node else {
            return 0
        }
        
        // 左子树高度减去右子树高度
        return self.getHeightWithNode(node.left) - self.getHeightWithNode(node.right)
    }
    
    /// 检查是否是平衡二叉树
    func isBalanceTree() -> Bool {
        
        return self.isBalanceTree(self.root)
    }
    
    private func isBalanceTree(_ node: Node?) -> Bool {
        guard let node = node else {return true}
        
        let factor = self.getBalanceFactor(node: node)
        // 如果平衡因子的绝对值大于1 那么不平衡
        if abs(factor) > 1 {
            return false
        }
        
        return self.isBalanceTree(node.left) && self.isBalanceTree(node.right)
    }
}
